textabstractDithered hash functions were proposed by Rivest as a method\udto mitigate second preimage attacks on Merkle-Damgard hash functions.\udDespite that, second preimage attacks against dithered hash functions\udwere proposed by Andreeva et al. One issue with these second preimage\udattacks is their huge memory requirement in the precomputation and the\udonline phases. In this paper, we present new second preimage attacks on\udthe dithered Merkle-Damgard construction. These attacks consume significantly\udless memory in the online phase (with a negligible increase in\udthe online time complexity) than previous attacks. For example, in the\udcase of MD5 with the Keranen sequence, we reduce the memory complexity\udfrom about 2^51 blocks to about 2^26.7 blocks (about 545 MB). We also\udpresent an essentially memoryless variant of Andreeva et al. attack. In\udcase of MD5-Keranen or SHA1-Keranen, the offline and online memory\udcomplexity is 2^15.2 message blocks (about 188–235 KB), at the expense\udof increasing the offline time complexity.
展开▼
